package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/n-ary-tree-preorder-traversal/">N 叉树的前序遍历(N-ary Tree Preorder Traversal)</a>
 * <p>给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。</p>
 * <p>n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。</p>
 * <p>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,3,2,4,null,5,6]
 *                    1
 *                 /  |  \
 *                3   2   4
 *               / \
 *              5   6
 *      输出：[1,3,5,6,2,4]
 *
 * 示例 2：
 *      输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 *      输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>节点总数在范围 [0, 10^4]内</li>
 *     <li>0 <= Node.val <= 10^4</li>
 *     <li>n 叉树的高度小于或等于 1000</li>
 * </ul>
 * </p>
 * <b>进阶：递归法很简单，你可以使用迭代法完成此题吗?</b>
 *
 * @author c2b
 * @see LC0429NaryTreeLevelOrderTraversal_M N 叉树的层序遍历(N-ary Tree Level Order Traversal)
 * @see LC0589NaryTreePreorderTraversal_S  N 叉树的前序遍历(N-ary Tree Preorder Traversal)
 * @see LC0590NaryTreePostorderTraversal_S N 叉树的后序遍历(N-ary Tree Postorder Traversal)
 * @since 2023/5/23 14:50
 */
public class LC0589NaryTreePreorderTraversal_S {

    public List<Integer> preorder(Node root) {
        List<Integer> resList = new ArrayList<>();
        //preorderByRecursion(root, resList);
        preorderByIteration(root, resList);
        return resList;
    }


    public void preorderByRecursion(Node root, List<Integer> resList) {
        if (root == null) {
            return;
        }
        resList.add(root.val);
        for (Node child : root.children) {
            preorderByRecursion(child, resList);
        }
    }

    public void preorderByIteration(Node root, List<Integer> resList) {
        if (root == null) {
            return;
        }
        Deque<Node> stack = new ArrayDeque<>();
        stack.addLast(root);
        while (!stack.isEmpty()) {
            Node currNode = stack.removeLast();
            resList.add(currNode.val);
            if (currNode.children != null) {
                for (int i = currNode.children.size() - 1; i >= 0; --i) {
                    stack.addLast(currNode.children.get(i));
                }
            }
        }
    }


    static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public static void main(String[] args) {
        Node node = new Node(1, new ArrayList<>());
        Node node1 = new Node(3, new ArrayList<>());
        Node node2 = new Node(2, new ArrayList<>());
        Node node3 = new Node(4, new ArrayList<>());
        Node node4 = new Node(5, new ArrayList<>());
        Node node5 = new Node(6, new ArrayList<>());
        List<Node> children1 = new ArrayList<>();
        children1.add(node1);
        children1.add(node2);
        children1.add(node3);
        List<Node> children2 = new ArrayList<>();
        children2.add(node4);
        children2.add(node5);
        node.children = children1;
        node1.children = children2;
        LC0589NaryTreePreorderTraversal_S lc0589NaryTreePreorder_Traversal_s = new LC0589NaryTreePreorderTraversal_S();
        Printer.printListInteger(lc0589NaryTreePreorder_Traversal_s.preorder(node));
    }

}
